import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test15 {
    //1.定义全局变量
    /*
    column：用来判断列的
    diagonals1：用来判断正对角线
    diagonals2：用来判断反对角线
     */
    boolean[] columns, diagonals1, diagonals2;
    //结果收集的二维数组
    List<List<String>> ret;
    //收集"本次"皇后位置的数组，因为棋盘是二维的，所以path是二维数组
    char[][] path;
    //表示棋盘的行或者列
    int n;

    public List<List<String>> solveNQueens(int _n) {
        //2.初始化
        n = _n;
        columns = new boolean[n];
        diagonals1 = new boolean[2 * n];
        diagonals2 = new boolean[2 * n];
        ret = new ArrayList<>();
        path = new char[n][n];
        //把path的所有位置先该为.
        for (int i = 0; i < n; i++) {
            Arrays.fill(path[i], '.');
        }
        //开始回溯算法的核心部分
        dfs(0);//从第一行开始
        return ret;
    }

    public void dfs(int row) {
        //如果到了棋盘的最后一行了，证明本次皇后们的位置是合法的
        if (row == n) {
            //添加结果
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
        } else {
            //开始匹配
            for (int col = 0; col < n; col++) {
                //判断能不能放
                if (columns[col] == false && diagonals1[col - row + n] == false
                        && diagonals2[col + row] == false) {
                    path[row][col] = 'Q';
                    columns[col] = diagonals1[col - row + n] =
                            diagonals2[col + row] = true;
                    //寻找下一行
                    dfs(row + 1);
                    //恢复现场
                    path[row][col] = '.';
                    columns[col] = diagonals1[col - row + n]
                            = diagonals2[col + row] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        Test15 test15 = new Test15();
        test15.solveNQueens(8);
        for (int i = 0; i < test15.ret.size(); i++) {
            System.out.println(test15.ret.get(i) + " ");
        }
    }
}
